// //
// // Created by Symps on 2025/11/17.
// //
// #include <iostream>
// #include <vector>
// #include <queue>
// using namespace std;
//
// vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc,
//                               int color) {
//     int origin(image[sr][sc]);
//     if (origin == color) {
//         return image;
//     }
//
//     int m(image.size());
//     int n(image[0].size());
//
//     queue<pair<int, int>> q;
//     q.emplace(sr, sc);
//     while (q.size()) {
//         auto& [r, c] = q.front();
//         q.pop();
//         image[r][c] = color;
//
//         if (r - 1 >= 0 && image[r - 1][c] == origin) {
//             q.emplace(r - 1, c);
//         }
//
//         if (r + 1 < m && image[r + 1][c] == origin) {
//             q.emplace(r + 1, c);
//         }
//
//         if (c - 1 >= 0 && image[r][c - 1] == origin) {
//             q.emplace(r, c - 1);
//         }
//
//         if (c + 1 < n && image[r][c + 1] == origin) {
//             q.emplace(r, c + 1);
//         }
//     }
//
//     return image;
// }
//
// template<class T>
// void vector_print(vector<vector<T>>& v) {
//     for (auto& vv : v) {
//         for (auto& vvv : vv) {
//             cout << vvv << " ";
//         }
//         cout << endl;
//     }
//     cout << endl;
// }
//
// void test1() {
//     // vector<vector<int>> image = {{1,1,1},{1,1,0},{1,0,1}};
//     vector<vector<int>> image = {{0, 0, 0}, {0, 0, 0}};
//     floodFill(image, 0, 0, 0);
//     vector_print(image);
// }
//
// template <class... Args>
// void printa(Args... args) {
//     cout << "args: " << sizeof...(args) << endl;
//     ((cout << args << " "), ...);
//     cout << endl;
// }
//
// void show_list() {
//     cout << endl;
// }
//
// int numIslands(vector<vector<char>>& grid) {
//     size_t m(grid.size()), n(grid[0].size());
//     int dr[4]{1, -1, 0, 0};
//     int dc[4]{0, 0, 1, -1};
//     int cnt{};
//     vector<vector<bool>> isvisited{m, vector<bool>(n, false)};
//     for (int i{}; i < m; ++i) {
//         for (int j{}; j < n; ++j) {
//             if (isvisited[i][j] == false && grid[i][j] == '1') {
//                 ++cnt;
//                 queue<pair<int, int>> q;
//                 q.emplace(i, j);
//                 while (!q.empty()) {
//                     auto& [r, c]{q.front()};
//                     q.pop();
//
//                     for (int l{}; l < 4; ++l) {
//                         int a(r + dr[l]), b(c + dc[l]);
//                         if (a >= 0 && a < m && b >= 0 && b < n && isvisited[a][b] == false && grid[a][b] == '1') {
//                             q.emplace(a, b);
//                             isvisited[a][b] = true;
//                         }
//                     }
//                 }
//             }
//         }
//     }
//     return cnt;
// }
//
// void test2() {
//     vector<vector<char>> grid = {
//         {'1', '1', '1', '1', '0'},
//         {'1', '1', '0', '1', '0'},
//         {'1', '1', '0', '0', '0'},
//         {'0', '0', '0', '0', '0'}
//     };
//     cout << numIslands(grid) << endl;
// }
//
// class Solution1 {
// private:
//     int dr[4]{0, 0, 1, -1};
//     int dc[4]{1, -1, 0, 0};
//     size_t m, n;
//
// public:
//     void solve(vector<vector<char>>& board) {
//         m = board.size();
//         n = board[0].size();
//
//         vector<vector<bool>> begirt{m, vector<bool>(n, true)};
//         for (int i{}; i < n; ++i) {
//             if (board[0][i] == 'O' && begirt[0][i]) {
//                 expendUnbegirt(board, begirt, 0, i);
//             }
//
//             if (board[m - 1][i] == 'O' && begirt[m - 1][i]) {
//                 expendUnbegirt(board, begirt, m - 1, i);
//             }
//         }
//
//         for (int i{1}; i < m - 1; ++i) {
//             if (board[i][0] == 'O' && begirt[i][0]) {
//                 expendUnbegirt(board, begirt, i, 0);
//             }
//
//             if (board[i][n - 1] == 'O' && begirt[i][n - 1]) {
//                 expendUnbegirt(board, begirt, i, n - 1);
//             }
//         }
//
//         for (int i{1}; i < m - 1; ++i) {
//             for (int j{1}; j < n - 1; ++j) {
//                 if (board[i][j] == 'O' && begirt[i][j]) {
//                     queue<pair<int, int>> q;
//                     q.emplace(i, j);
//                     q.pop();
//                     begirt[i][j] = false;
//                     board[i][j] = 'X';
//
//                     while (q.size()) {
//                         auto [a, b]{q.front()};
//
//                         for (int k{}; k < 4; k++) {
//                             int r{a + dr[k]}, c{b + dc[k]};
//                             if (begirt[r][c] && board[r][c] == 'O') {
//                                 q.emplace(r, c);
//                                 begirt[r][c] = false;
//                                 board[r][c] = 'X';
//                             }
//                         }
//                     }
//                 }
//             }
//         }
//     }
//
// private:
//     void expendUnbegirt(vector<vector<char>>& board,
//                         vector<vector<bool>>& begirt, int i, int j) {
//         queue<pair<int, int>> q;
//         q.emplace(i, j);
//         begirt[i][j] = false;
//         while (q.size()) {
//             auto [a, b]{q.front()};
//             q.pop();
//
//             for (int k{}; k < 4; ++k) {
//                 int r{a + dr[k]}, c{b + dc[k]};
//                 if (r >= 0 && r < m && c >= 0 && c < n && begirt[r][c] && board[r][c] == 'O') {
//                     q.emplace(r, c);
//                     begirt[r][c] = false;
//                 }
//             }
//         }
//     }
// };
//
// void test3() {
//     Solution1 s;
//     // [["X","O","X","O","X","O"],["O","X","O","X","O","X"],["X","O","X","O","X","O"],["O","X","O","X","O","X"]]
//     vector<vector<char>> board = {
//         {'X', 'O', 'X', 'O', 'X', 'O'},
//         {'O', 'X', 'O', 'X', 'O', 'X'},
//         {'X', 'O', 'X', 'O', 'X', 'O'},
//         {'O', 'X', 'O', 'X', 'O', 'X'}
//     };
//     s.solve(board);
//     vector_print(board);
//
// }
//
// int main() {
//     // test1();
//     // test2();
//     test3();
//     return 0;
// }


#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;

template <class T>
struct TreeNode {
    TreeNode(T val = 0) : _val(val), _left(nullptr), _right(nullptr) {}

    TreeNode(T val, TreeNode* left, TreeNode* right)
        : _val(val), _left(left), _right(right) {}

    T _val;
    TreeNode* _left;
    TreeNode* _right;
};

struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
        auto h1 = hash<int>{}(p.first);
        auto h2 = hash<int>{}(p.second);
        return h1 ^ (h2 << 1); // 简单异或合并
    }
};

int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
    unordered_set<pair<int, int>, PairHash> hash;
    queue<pair<int, int>> q;
    int dr[4]{-1, 1, 0, 0};
    int dc[4]{0, 0, 1, -1};
    int step{0};

    size_t m{maze.size()}, n{maze[0].size()};

    hash.emplace(entrance[0], entrance[1]);
    q.emplace(entrance[0], entrance[1]);

    while (q.size()) {
        ++step;
        size_t sz{q.size()};
        while (sz--) {
            auto [a, b]{q.front()};
            q.pop();
            for (int k{}; k < 4; ++k) {
                int r{a + dr[k]}, c{b + dc[k]};
                if (r >= 0 && r < m && c >= 0 && c < n) {
                    if (hash.find({r, c}) == hash.end() && maze[r][c] == '.') {
                        q.emplace(r, c);
                    }
                } else {
                    return step;
                }
            }
        }
    }
    return step;
}

void test1() {
    // empty
}

char p[4]{'A', 'T', 'G', 'C'};

int minMutation(string startGene, string endGene, vector<string>& bank) {
    unordered_map<string, bool> bk;
    for (auto& x : bank) {
        bk.emplace(x, false);
    }
    if (bk.find(endGene) == bk.end()) {
        return -1;
    }
    int times{};
    queue<string> q;
    q.push(startGene);
    if (bk.find(startGene) != bk.end() && bk.find(startGene)->second == false) {
        bk.find(startGene)->second = true;
    }

    while (q.size()) {
        size_t sz{q.size()};
        while (sz--) {
            auto str{q.front()};
            q.pop();
            if (str == endGene) {
                return times;
            }
            for (int i{}; i < 8; ++i) {
                auto temp{str};
                for (int j{}; j < 4; ++j) {
                    if (p[j] != str[i]) {
                        temp[i] = p[j];
                        if (bk.find(temp) != bk.end() && bk.find(temp)->second == false) {
                            q.push(temp);
                            bk.find(temp)->second = true;
                        }
                    }
                }
            }
        }
        ++times;
    }
    return -1;
}

void test2() {
    string startGene("AAAAAAAA");
    string endGene("CCCCCCCC");
    vector<string> bank{
        "AAAAAAAA", "AAAAAAAC", "AAAAAACC", "AAAAACCC", "AAAACCCC",
        "AAACCCCC", "AACCCCCC", "ACCCCCCC", "CCCCCCCA"
    };
    cout << minMutation(startGene, endGene, bank) << endl;
}

class Solution {
    using pos = pair<int, int>;

public:
    map<int, pos> pool;
    int dr[4]{0, 0, 1, -1};
    int dc[4]{1, -1, 0, 0};
    size_t m, n;

    int cutOffTree(vector<vector<int>>& forest) {
        m = forest.size();
        n = forest[0].size();
        for (int i{}; i < m; ++i) {
            for (int j{}; j < n; ++j) {
                if (forest[i][j] > 1) {
                    pool.emplace(forest[i][j], make_pair(i, j));
                }
            }
        }

        int cnt{};
        pos currPos(0, 0);
        while (!pool.empty()) {
            auto next{pool.begin()->second};
            int step{getStep(currPos, next, forest)};
            if (step == -1) {
                return -1;
            }
            cnt += step;
            currPos = next;
            pool.erase(pool.begin());
        }
        return cnt;
    }

private:
    // 返回时机：在目标位置出队后返回steps或者目标位置在出队前被检测到返回steps + 1，当前实现为前者
    int getStep(pos src, pos dest, vector<vector<int>>& forest) {
        // if (src == dest) {
        //     return 0;
        // }
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        queue<pos> q;
        q.push(src);
        vis[src.first][src.second] = true;
        int steps{};
        while (q.size()) {
            size_t sz{q.size()};
            while (sz--) {
                auto [a, b]{q.front()};
                if (make_pair(a, b) == dest) {
                    return steps;
                }
                q.pop();
                for (int k{}; k < 4; ++k) {
                    int r{a + dr[k]}, c{b + dc[k]};

                    if (r >= 0 && r < m && c >= 0 && c < n) {
                        // if (make_pair(r, c) == dest) {
                        //     return steps + 1;
                        // }
                        if (forest[r][c] != 0 && vis[r][c] == false) {
                            q.emplace(r, c);
                            vis[r][c] = true;
                        }
                    }
                }
            }
            ++steps;
        }
        return -1;
    }
};

void test3() {
    int a = 1;
    int b = sizeof a;
    cout << b << endl;
}

class Solution2 {
public:
    using order = pair<char, char>;
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> edges;
        unordered_map<char, int> inDegree;
        for (auto& word : words) {
            for (auto c : word) {
                inDegree[c];
            }
        }
        int wordsCount(words.size());
        for (int i{}; i < wordsCount - 1; ++i) {
            for (int j{i + 1}; j < wordsCount; ++j) {
                if (!addEdge(words[i], words[j], edges, inDegree)) {
                    return {};
                }
            }
        }


        queue<char> q;
        for (auto& [k, v] : inDegree) {
            if (v == 0) {
                q.emplace(k);
            }
        }

        string ret{};
        while (!q.empty()) {
            auto& key{q.front()};
            q.pop();
            ret += key;
            for (auto& v : edges[key]) {
                --inDegree[v];
                if (inDegree[v] == 0) {
                    q.emplace(v);
                }
            }
        }

        if (ret.size() == inDegree.size()) {
            return ret;
        }
        return {};
    }

    bool addEdge(string& str1, string& str2, unordered_map<char, unordered_set<char>>& edges, unordered_map<char, int> &inDegree) {
        int k{};
        while (k < str1.size() && k <str2.size()) {
            if (str1[k] == str2[k]) {
                ++k;
                continue;
            }
            auto [ _, flag]{edges[str1[k]].emplace(str2[k])};
            if (flag) {
                ++inDegree[str2[k]];
            }
            return true;
        }
        return str1.size() <= str2.size();
    }
};

void test4() {
    // ["wrt","wrf","er","ett","rftt"]
    vector<string> words{"wrt","wrf","er","ett","rftt"};
    // cout << Solution2().alienOrder(words) << endl;
    // ["abc","ab"]
    words = {"abc","ab"};
    cout << Solution2().alienOrder(words) << endl;
}

int main() {
    // test1();
    // test2();
    // test3();
    test4();
    return {};
}
